This invention relates generally to color image quantization, and more particularly to such quantization using a hierarchical color perception model.
Color images, such as those captured using a digital video camera, a capture device for an analog video camera, a digital camera, or a scanner for existing photos, typically have a multitude of colors. For example, an image that is captured using a 24-bit color depth can have up to 224 different colors. While this makes for a very realistic image, the vast number of colors in the image means that the image takes up a lot of memory, which is inconvenient for storage and transmission purposes. Furthermore, applications such as computer vision (and image understanding) applications have difficulty understanding the perceptual objects (e.g., a person in a photo, a tree in the photo, etc.) that make up an image when there are so many colors in the image.
Therefore, color image quantization reduces the number of colors in an image to a predetermined number, such as only sixteen, as one example. It does this by determining an appropriate palette, or table, of a reduced number of colors, and then mapping the color of each pixel to a color from the palette, typically to the palette color that is closest to the original color of the pixel. In this way, the storage size of the image is effectively compressed, since far less data is needed to describe the colors of the image. An added advantage is that applications such as computer vision applications may then have an easier time understanding the objects that make up an image, where the objects each have fairly distinct color boundaries from one another.
Generally, color image quantization approaches within the prior art achieve a similarity between the source image and the quantized image based on the intensity difference between the two images, or based on another pixel-based measurement, such as a color histogram. However, such approaches do not provide higher-level information, such as the spatial connectivity among pixels, which is necessary for applications such as image segmentation and object recognition. While some approaches do take into account some of the spatial distribution among the colors of the images, they still usually do not provide enough higher-level information that is required in computer vision and other applications.
For these and other reasons, therefore, there is a need for the present invention.
The invention relates to color image quantization using a hierarchical perceptual color model. In one embodiment, a method constructs a clustering space of an image made up of a number of pixels, based on a color perception model. The clustering space includes a number of significant pixels, such that each of the significant pixels does not have a parent pixel within the clustering space, while the hierarchically lesser remaining pixels have at least one parent that is a significant pixel. The colors of the image are then quantized based on these significant pixels. Each of the remaining pixels then has its colors mapped to one of the quantized colors.
In one particular embodiment, constructing the clustering space of the image involves growing a perceptible color region, such as a disk, for each pixel, and building a relationship graph of hierarchical parent-child relationships of the pixels based on these perceptible color regions. A perceptible color region in one particular embodiment is grown by using a multi-scale edges approach. The relationship graph in one particular embodiment is built for each pair of overlapping regions by determining which region has a greater size, such that the region which has the greater size is the parent, and the region having the lesser size is the child.
Embodiments of the invention provide for advantages not found within the prior art. A color quantized image according to an embodiment of the invention has its colors chosen based on the non-overlapping perceptible color regions. Because these regions are themselves grown based on a color perception model, this means that the colors that are selected are comparable to what is visually significant to a human. Thus, inasmuch as colors are useful in determining the boundaries among objects within the image, quantizing the image according to colors selected based on a color perception model means that the resulting color quantized image yields useful higher-level information for computer vision and other applications.
The invention includes computer-implemented methods, machine-readable media, computerized systems, and computers of varying scopes. Other aspects, embodiments and advantages of the invention, beyond those described here, will become apparent by reading the detailed description and with reference to the drawings.